import java.util.List;

class Ast {
  
  public static class Error extends Exception {
    Error(String text) {
      super(text);
    }
  }

  public abstract static class Node {
    int line;
    Node (int line) {
      this.line = line;
    }
    private static final String newline =  System.getProperty("line.separator");
    private static String tabs(int tab) {
      String r = newline;
      for (int i = 0; i< tab; i++)
        r += "  ";
      return r;
    }
    abstract String toPretty(int tab);     
    String format(int tab,String desc) {
      return tabs(tab) + "(" + line + " " + desc + ")";
    }
    String formatList(int tab, Node[] nodes) {
      String r = "(";
      for (int i = 0; i < nodes.length; i++)
        r += nodes[i].toPretty(tab);
      r += ")";
      return r;
    }
    public String toString() {
      String r = this.toPretty(0);
      return r.substring(newline.length());
    }
  }


  public static class Program extends Node {
    Body body;
    Program (int line, Body body) {
      super(line);
      this.body = body;
    }
    String toPretty(int tab) {
      return format(tab,"Program" + body.toPretty(tab+1));
    }
  }

  public static class Body extends Node {
    Decs[] decslist;
    St statement;
    Body (int line, Decs[] decslist, St statement) {
      super(line); 
      this.decslist = decslist; this.statement = statement;
    }
    Body (int line, List decslist, St statement) {
	this(line,(Decs[]) decslist.toArray(new Decs[0]),statement);
    }
    public String toPretty(int tab) {
      return format(tab, "BodyDef " + formatList(tab+1,decslist) + statement.toPretty(tab+1));
    }
  }

  public abstract static class Decs extends Node {
    Decs(int line) {
      super(line);
    }
    abstract Object accept(DecsVisitor v) throws Error; 
  }

  interface DecsVisitor {
    Object visit(Ast.VarDecs d) throws Error;
    Object visit(Ast.TypeDecs d) throws Error;
    Object visit(Ast.ProcDecs d) throws Error;
  }

  public static class VarDecs extends Decs {
    VarDec[] vardeclist;
    VarDecs (int line, VarDec[] vardeclist) {
      super(line);
      this.vardeclist = vardeclist;
    }
    VarDecs (int line, List vardeclist) {
      this(line,(VarDec[]) vardeclist.toArray(new VarDec[0]));
    }
    String toPretty(int tab) {
      return format(tab, "VarDecs " + formatList(tab+1,vardeclist));
    }
    Object accept(DecsVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class TypeDecs extends Decs {
    TypeDec[] typedeclist;
    TypeDecs (int line,TypeDec[] typedeclist) {
      super(line);
      this.typedeclist = typedeclist;
    }
    TypeDecs (int line, List typedeclist) {
      this(line,(TypeDec[]) typedeclist.toArray(new TypeDec[0]));
    }
    String toPretty(int tab) {
      return format(tab, "TypeDecs " + formatList(tab+1,typedeclist));
    }
    Object accept(DecsVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class ProcDecs extends Decs {
    ProcDec[] procdeclist;
    ProcDecs (int line, ProcDec[] procdeclist) {
      super(line);
      this.procdeclist = procdeclist;
    }
    ProcDecs (int line, List procdeclist) {
      this(line,(ProcDec[]) procdeclist.toArray(new ProcDec[0]));
    }
    String toPretty(int tab) {
      return format(tab, "ProcDecs " + formatList(tab+1,procdeclist));
    }
    Object accept(DecsVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public abstract static class Dec extends Node {
    String name;
    Dec(int line, String name) {
      super(line);
      this.name = name;
    }
    abstract Object accept(DecVisitor v) throws Error; 
  }

  interface DecVisitor {
    Object visit(Ast.VarDec d) throws Error;
    Object visit(Ast.TypeDec d) throws Error;
    Object visit(Ast.ProcDec d) throws Error;
    Object visit(Ast.FormalParam d) throws Error;
    Object visit(Ast.ConstDec d) throws Error;
  }

  public static class VarDec extends Dec {
    String type;   // can be null on construction, but should be filled in by checker
    Exp initializer;
    VarDec(int line, String name, String type, Exp initializer) {
      super(line,name); 
      this.type = type; this.initializer = initializer;
    }
    String toPretty(int tab) {
      return format(tab,"VarDec " + name + " " + 
		    (type != null ? type : "-") + initializer.toPretty(tab+1));
    }
    Object accept(DecVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class TypeDec extends Dec {
    Type defn;
    TypeDec(int line, String name, Type defn) {
      super(line,name); 
      this.defn = defn;
    }
    String toPretty(int tab) {
      return format(tab, "TypeDec " + name + defn.toPretty(tab+1));
    }
    Object accept(DecVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class ProcDec extends Dec {
    String resultType;  // can be null
    FormalParam[] formals;
    Body body;
    ProcDec(int line, String name, String resultType, FormalParam[] formals, Body body) {
      super(line,name); 
      this.resultType = resultType; this.formals = formals; this.body = body;
    }
    ProcDec(int line, String name, String resultType, List formals, Body body) {
      this(line, name, resultType, (FormalParam[]) formals.toArray(new FormalParam[0]), body);
    }
    String toPretty(int tab) {
      return format(tab, "ProcDec " + name + " " + (resultType != null ? resultType : "-") + 
		          " " + formatList(tab+1,formals) + body.toPretty(tab+1));
    }
    Object accept(DecVisitor v) throws Error {
      return v.visit(this);
    }
  }


  public static class FormalParam extends Dec {
    String type;
    FormalParam (int line, String name, String type) {
      super(line,name);
      this.type = type;
    }
    String toPretty(int tab) {
      return format(tab, "Param " + name + " " + type);
    }
    Object accept(DecVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class ConstDec extends Dec { // builtins only
    String type;
    ConstDec(String name,String type) {
      super(0,name);
      this.type = type;
    }
    String toPretty(int tab) {
      return format(tab, "Const " + name + " " + type);
    }
    Object accept(DecVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public abstract static class Type extends Node {
    Type(int line) {
      super(line);
    }
    abstract Object accept(TypeVisitor v) throws Error; 
  }

  interface TypeVisitor {
    Object visit(Ast.ArrayType t) throws Error;
    Object visit(Ast.RecordType t) throws Error;
    Object visit(Ast.BuiltinType t) throws Error;
  }

  public static class ArrayType extends Type {
    String elementType;
    ArrayType (int line, String elementType) {
      super(line); 
      this.elementType = elementType;
    }
    String toPretty(int tab) {
      return format(tab, "ArrayTyp " + elementType);
    }
    Object accept(TypeVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class RecordType extends Type {
    Component[] components;
    RecordType (int line, Component[] components) {
      super(line); 
      this.components = components;
    }
    RecordType (int line, List components) {
      this(line, (Component[]) components.toArray(new Component[0]));
    }
    String toPretty(int tab) {
      return format(tab, "RecordTyp " + formatList(tab+1,components));
    }
    Object accept(TypeVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class BuiltinType extends Type {
    BuiltinType() {
      super(0);
    }
    String toPretty(int tab) {
      return format(tab, "BuiltinTyp");
    }
    Object accept(TypeVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class Component extends Node {
    String name;
    String type;
    Component (int line, String name, String type) {
      super(line);
      this.name = name; this.type = type;
    }
    String toPretty(int tab) {
      return format(tab, "Comp " + name + " " + type);
    }
  }
  

  public abstract static class St extends Node {
    St (int line) {
      super(line);
    }
    abstract Object accept(StVisitor v) throws Error;
  }


  interface StVisitor {
    Object visit(Ast.AssignSt s) throws Error;
    Object visit(Ast.CallSt s) throws Error;
    Object visit(Ast.ReadSt s) throws Error;
    Object visit(Ast.WriteSt s) throws Error;
    Object visit(Ast.IfSt s) throws Error;
    Object visit(Ast.WhileSt s) throws Error;
    Object visit(Ast.LoopSt s) throws Error;
    Object visit(Ast.ForSt s) throws Error;
    Object visit(Ast.ExitSt s) throws Error;
    Object visit(Ast.ReturnSt s) throws Error;
    Object visit(Ast.SequenceSt s) throws Error;
  }

  public static class AssignSt extends St {
    Lvalue lhs;
    Exp rhs;
    AssignSt(int line, Lvalue lhs, Exp rhs) {
      super(line); 
      this.lhs = lhs; this.rhs = rhs;
    }
    String toPretty(int tab) {
      return format(tab,"AssignSt" + lhs.toPretty(tab+1) + rhs.toPretty(tab+1));
    }
    Object accept(StVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class CallSt extends St {
    String procName;
    Exp[] args;
    CallSt(int line, String procName, Exp[] args) {
      super(line); 
      this.procName = procName; this.args = args;
    }
    CallSt(int line, String procName, List args) {
      this(line, procName, (Exp[]) args.toArray(new Exp[0]));
    }
    String toPretty(int tab) {
      return format(tab, "CallSt " + procName + " " + formatList(tab+1,args));
    }
    Object accept(StVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class ReadSt extends St {
    Lvalue[] targets;
    ReadSt(int line, Lvalue[] targets) {
      super(line); 
      this.targets = targets;
    }
    ReadSt(int line, List targets) {
      this(line, (Lvalue[]) targets.toArray(new Lvalue[0]));
    }
    String toPretty(int tab) {
      return format(tab, "ReadSt " + formatList(tab+1,targets));
    }
    Object accept(StVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class WriteSt extends St {
    Exp[] exps;
    WriteSt(int line, Exp[] exps) {
      super(line); 
      this.exps = exps;
    }
    WriteSt(int line, List exps) {
      this(line,(Exp[]) exps.toArray(new Exp[0]));
    }
    String toPretty(int tab) {
      return format(tab, "WriteSt " + formatList(tab+1,exps));
    }
    Object accept(StVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class IfSt extends St {
    Exp test;
    St ifTrue;
    St ifFalse;
    IfSt(int line, Exp test, St ifTrue, St ifFalse) {
      super(line); 
      this.test = test; this.ifTrue = ifTrue; this.ifFalse = ifFalse;
    }
    String toPretty(int tab) {
      return format(tab,"IfSt" + test.toPretty(tab+1) + ifTrue.toPretty(tab+1) + ifFalse.toPretty(tab+1));
    }
    Object accept(StVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class WhileSt extends St {
    Exp test;
    St body;
    WhileSt(int line, Exp test, St body) {
      super(line); 
      this.test = test; this.body = body;
    }
    String toPretty(int tab) {
      return format(tab, "WhileSt" + test.toPretty(tab+1) + body.toPretty(tab+1));
    }
    Object accept(StVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class LoopSt extends St {
    St body;
    LoopSt(int line, St body) {
      super(line); 
      this.body = body;
    }
    String toPretty(int tab) {
      return format(tab,"LoopSt" + body.toPretty(tab+1));
    }
    Object accept(StVisitor v) throws Error {
      return v.visit(this);
    }
  }
  
  public static class ForSt extends St {
    String loopVar;
    Exp start;
    Exp stop;
    Exp step;
    St body;
    ForSt (int line, String loopVar, Exp start, Exp stop, Exp step, St body) {
      super(line); 
      this.loopVar = loopVar; this.start = start;
      this.stop = stop; this.step = step; this.body = body;
    }
    String toPretty(int tab) {
      return format(tab, "ForSt " + loopVar + start.toPretty(tab+1) + 
		          stop.toPretty(tab+1) + step.toPretty(tab+1) + body.toPretty(tab+1));
    }
    Object accept(StVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class ExitSt extends St {
    ExitSt(int line) {
      super(line);
    }
    String toPretty(int tab) {
      return format(tab,"ExitSt");
    }
    Object accept(StVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class ReturnSt extends St {
    Exp returnValue; // can be null
    ReturnSt(int line, Exp returnValue) {
      super(line); 
      this.returnValue = returnValue;
    }
    String toPretty(int tab) {
      return format(tab,"RetSt" + (returnValue != null ? returnValue.toPretty(tab+1) : " - "));
    }
    Object accept(StVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class SequenceSt extends St {
    St[] statements;
    SequenceSt (int line, St[] statements) {
      super(line);
      this.statements = statements;
    }
    SequenceSt (int line, List statements) {
      this(line,(St[]) statements.toArray(new St[0]));
    }
    String toPretty(int tab) {
      return format(tab, "SeqSt " + formatList(tab+1,statements));
    }
    Object accept(StVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public abstract static class Exp extends Node {
    Exp (int line) {
      super(line);
    }
    abstract Object accept(ExpVisitor v) throws Error;
  }

  interface ExpVisitor {
    Object visit(Ast.BinOpExp e) throws Error;
    Object visit(Ast.UnOpExp e) throws Error;
    Object visit(Ast.LvalExp e) throws Error;
    Object visit(Ast.CallExp e) throws Error;
    Object visit(Ast.ArrayExp e) throws Error;
    Object visit(Ast.RecordExp e) throws Error;
    Object visit(Ast.IntLitExp e) throws Error;
    Object visit(Ast.RealLitExp e) throws Error;
    Object visit(Ast.StringLitExp e) throws Error;
  }

  // BinOp codes
  public static final int  
    LT = 0,
    LEQ = 1,
    GT = 2,
    GEQ = 3,
    EQ = 4,
    NEQ = 5,
    PLUS = 6,
    MINUS = 7,
    TIMES = 8,
    SLASH = 9,
    DIV = 10,
    MOD = 11,
    AND = 12,
    OR = 13;
  
  public static class BinOpExp extends Exp {
    int binOp;
    Exp left;
    Exp right;
    BinOpExp(int line, int binOp, Exp left, Exp right) {
      super(line);
      this.binOp = binOp; this.left = left; this.right = right;
    }
    private static String[] binOpName = {"LT","LEQ","GT","GEQ","EQ","NEQ","PLUS","MINUS","TIMES","SLASH",
				  "DIV","MOD","AND","OR"};
    String toPretty(int tab) {
      return format(tab,"BinOpExp " + binOpName[binOp] + left.toPretty(tab+1) + right.toPretty(tab+1));
    }
    Object accept(ExpVisitor v) throws Error {
      return v.visit(this);
    }
  }

  // UnOp codes
  public static final int
    UMINUS = 0,
    NOT = 1;

  public static class UnOpExp extends Exp {
    int unOp;
    Exp operand;
    UnOpExp(int line, int unOp, Exp operand) {
      super(line);
      this.unOp = unOp; this.operand = operand;
    }
    private static String[] unOpName = {"UMINUS","NOT"};
    String toPretty(int tab) {
      return format(tab, "UnOpExp " + unOpName[unOp] + operand.toPretty(tab+1));
    }
    Object accept(ExpVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class LvalExp extends Exp {
    Lvalue lval;
    LvalExp(int line, Lvalue lval) {
      super(line);
      this.lval = lval;
    }
    String toPretty(int tab) {
      return format(tab, "LvalExp" + lval.toPretty(tab+1));
    }
    Object accept(ExpVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class CallExp extends Exp {
    String procName;
    Exp[] args;
    CallExp(int line, String procName, Exp[] args) {
      super(line);
      this.procName = procName; this.args = args;
    }
    CallExp(int line, String procName, List args) {
      this(line, procName, (Exp[]) args.toArray(new Exp[0]));
    }
    String toPretty(int tab) {
      return format(tab, "CallExp " + procName + " " + formatList(tab+1,args));
    }
    Object accept(ExpVisitor v) throws Error {
      return v.visit(this);
    }
  }


  public static class ArrayExp extends Exp {
    String typeName;
    ArrayInit[] initializers;
    ArrayExp(int line, String typeName, ArrayInit[] initializers) {
      super(line);
      this.typeName = typeName; this.initializers = initializers;
    }
    ArrayExp(int line, String typeName, List initializers) {
      this(line, typeName, (ArrayInit[]) initializers.toArray(new ArrayInit[0]));
    }
    String toPretty(int tab) {
      return format(tab, "ArrayExp " + typeName + " " + formatList(tab+1,initializers));
    }
    Object accept(ExpVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class RecordExp extends Exp {
    String typeName;
    RecordInit[] initializers;
    RecordExp(int line, String typeName, RecordInit[] initializers) {
      super(line);
      this.typeName = typeName; this.initializers = initializers;
    }
    RecordExp(int line, String typeName, List initializers) {
      this(line, typeName, (RecordInit[]) initializers.toArray(new RecordInit[0]));
    }
    String toPretty(int tab) {
      return format(tab, "RecordExp " + typeName + " " + formatList(tab+1,initializers));
    }
    Object accept(ExpVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class IntLitExp extends Exp {
    int lit;
    IntLitExp(int line, int lit) {
      super(line);
      this.lit = lit;
    }
    IntLitExp(int line, Integer lit) {
      this(line, lit.intValue());
    }
    String toPretty(int tab) {
      return format(tab, "IntLit " + lit);
    }
    Object accept(ExpVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class RealLitExp extends Exp {
    String lit;
    RealLitExp(int line, String lit) {
      super(line);
      this.lit = lit;
    }
    String toPretty(int tab) {
      return format(tab, "RealLit \"" + lit + "\"");
    }
    Object accept(ExpVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class StringLitExp extends Exp {
    String lit;
    StringLitExp(int line, String lit) {
      super(line);
      this.lit = lit;
    }
    String toPretty(int tab) {
      return format(tab, "StringLit \"" + lit + "\"");
    }
    Object accept(ExpVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class ArrayInit extends Node {
    Exp count;
    Exp value;
    ArrayInit(int line, Exp count, Exp value) {
      super(line); 
      this.count = count; this.value = value;
    }
    String toPretty(int tab) {
      return format(tab, "ArrayInit" + count.toPretty(tab+1) + value.toPretty(tab+1));
    }
  }

  public static class RecordInit extends Node {
    String name;
    Exp value;
    int offset = -1; // filled in by checker
    RecordInit(int line, String name, Exp value) {
      super(line);
      this.name = name; this.value = value;
    }
    String toPretty(int tab) {
      return format(tab, "RecordInit " + name + " " + offset + value.toPretty(tab+1));
    }
  }

  public abstract static class Lvalue extends Node {
    Lvalue(int line) {
      super(line);
    }
    abstract Object accept(LvalueVisitor v) throws Error;
  }

  interface LvalueVisitor {
    Object visit(Ast.VarLvalue l) throws Error;
    Object visit(Ast.ArrayDerefLvalue l) throws Error;
    Object visit(Ast.RecordDerefLvalue l) throws Error;
  }

  public static class VarLvalue extends Lvalue {
    String name;
    VarLvalue(int line, String name) {
      super(line);
      this.name = name;
    }
    String toPretty(int tab) {
      return format(tab, "Var " + name);
    }
    Object accept(LvalueVisitor v) throws Error {
      return v.visit(this);
    }
  }

  public static class ArrayDerefLvalue extends Lvalue {
    Lvalue array;
    Exp index;
    ArrayDerefLvalue(int line, Lvalue array, Exp index) {
      super(line);
      this.array = array; this.index = index;
    }
    String toPretty(int tab) {
      return format(tab, "ArrayDeref" + array.toPretty(tab+1) + index.toPretty(tab+1));
    }
    Object accept(LvalueVisitor v) throws Error {
      return v.visit(this);
    }
  }
      
  public static class RecordDerefLvalue extends Lvalue {
    Lvalue record;
    String name;
    int offset = -1;  // filled in by checker
    RecordDerefLvalue(int line, Lvalue record, String name) {
      super(line);
      this.record = record; this.name = name;
    }
    String toPretty(int tab) {
      return format(tab, "RecordDeref" + record.toPretty(tab+1) + " " + name + " " + offset);
    }
    Object accept(LvalueVisitor v) throws Error {
      return v.visit(this);
    }
  }
}

